/** MTBLib.AllocList by Medi H.B.T. */

namespace MTBLib {
    public int block_init_length = 256;
    /** @class MTBLib.AllocList
     * 动态增长的ID分配表，本质上是共用内存空间的两个链表.
     * 占用的内存大小是斐波那契数列的整数倍。
     * 注意: 最小的ID是2. */
    public class AllocList: GLib.Object {
        public enum ErrorType {
            BASE          = 0x80010000,
            OVERFLOW      = 0x80010001,
            EMPTY         = 0x80010002,
            NOT_ALLOCATED = 0x80010003,
        }

        [CCode (cname="VNS_MTBLib_VCL_AllocList_Item")]
        public struct Item {
            int  prev;
            int  next;
            bool allocated;
        }

        /** fields */
        public Item []id_buff;
        public int prev_length;
        public int _back;

        public AllocList(int length = MTBLib.block_init_length) {
            prev_length = MTBLib.block_init_length;
            id_buff = new Item[prev_length];
            id_buff[0] = {-1, -1, false};   // "unallocated" list
            id_buff[1] = {-1, -1, true};    // "allocated"   list
            _back = 2;
        }

        /* private: tools to expand the buffer */
        protected virtual void do_expand()
        {
            int new_length = prev_length + id_buff.length;
            prev_length = id_buff.length;
            id_buff.resize((int)new_length);
        }
        protected virtual void do_shrink()
        {
            int old_prev_length = id_buff.length - prev_length;
            id_buff.resize(prev_length);
            prev_length = old_prev_length;
        }

        /** methods */
        public bool is_empty() { return (id_buff[1].next == -1); }
        public bool is_allocated(int id)
        {
            return (id >= 2)  && (id < _back) && (id_buff[id].allocated);
        }


        /**
         * @fn alloc()
         * @brief 分配一个新的ID
         * 在给定的AllocList对象中分配一个新的ID，并将其添加到已分配的元素链表中。
         * @return 返回分配的ID */
        public int alloc()
        {
            if (id_buff[0].next == -1) {
                // add new unallocated item
                if (_back == id_buff.length)
                    do_expand();
                id_buff[_back] = {0, -1, false};
                id_buff[0].next = _back;
                _back++;
            }

            /* remove the first "unused" id */
            int ret = id_buff[0].next;
            int ret_next = id_buff[ret].next;
            id_buff[0].next = ret_next;
            if (ret_next != -1)
                id_buff[ret_next].prev = 0;

            /* and let it join in the "used" list. */
            ret_next = id_buff[1].next;
            id_buff[ret] = {1, ret_next, true};
            if (ret_next != -1)
                id_buff[ret_next].prev = ret;
            id_buff[1].next = ret;

            return ret;
        }

        /** @fn free(int id)
         * @brief  释放已分配的ID, 并将该ID分配到未分配的链表中。
         * @return 返回错误状态。0表示没有错误，其余代码见ErrorType枚举。 */
        public ErrorType free(int id)
        {
            if (!is_allocated(id))
                return ErrorType.NOT_ALLOCATED;
            /* remove the target id */
            int id_prev = id_buff[id].prev;
            int id_next = id_buff[id].next;
            id_buff[id_prev].next = id_next;
            if (id_next != -1)
                id_buff[id_next].prev = id_prev;

            /* and let it join in the "unused" list. */
            id_next = id_buff[0].next;
            id_buff[id] = {0, id_next, false};
            if (id_next != -1)
                id_buff[id_next].prev = id;
            id_buff[0].next = id;
            return 0;
        }

        /** methods for debug */
        public void println(GLib.FileStream outfile = stdout,
                            int indent_level = 0)
        {
            Debug.indent(indent_level); outfile.puts("AllocList {\n");
            /* id_buff */
            Debug.indent(indent_level + 1); outfile.puts(".id_buff = {\n");
            for (int i = 0; i < _back; i++) {
                Debug.indent(indent_level + 2);
                outfile.printf("[%4d]={%4d, %4d, %s}\n",
                    i, id_buff[i].prev, id_buff[i].next,
                    id_buff[i].allocated ? "allocated": "not_allocated"
                );
            }
            Debug.indent(indent_level + 1); outfile.puts("}\n");
            Debug.indent(indent_level + 1); outfile.printf("._back = %d\n\n", _back);

            Debug.indent(indent_level + 1); outfile.puts("[Unallocated List] = {\n");
            Debug.indent(indent_level + 2);
            for (int i = 0; i != -1; i = id_buff[i].next)
                outfile.printf("%4d, ", i);
            outfile.putc('\n');
            Debug.indent(indent_level + 1); outfile.puts("}\n");

            Debug.indent(indent_level + 1); outfile.puts("[Allocated List] = {\n");
            Debug.indent(indent_level + 2);
            for (int i = 1; i != -1; i = id_buff[i].next)
                outfile.printf("%4d, ", i);
            outfile.putc('\n');
            Debug.indent(indent_level + 1); outfile.puts("}\n");

            Debug.indent(indent_level); outfile.puts("}\n");
            outfile.flush();
        }
    }
}
